// 回溯法解 0-1 背包问题
function knapsackBacktracking(weights, values, capacity) {
    let n = weights.length;
    let maxValue = 0; // 记录最大价值
    let currentWeight = 0; // 当前背包重量
    let currentValue = 0; // 当前背包价值

    // 回溯函数
    function backtrack(i) {
        // 剪枝1: 如果当前背包重量超过容量，停止搜索
        if (currentWeight > capacity) {
            return;
        }

        // 剪枝2: 如果当前已知最大价值已大于等于后续可能的最大值，停止搜索
        if (i >= n) {
            if (currentValue > maxValue) {
                maxValue = currentValue;
            }
            return;
        }

        // 左子树（选择当前物品）
        currentWeight += weights[i];
        currentValue += values[i];
        // 递归搜索：选择当前物品
        backtrack(i + 1);

        // 回溯：恢复状态
        currentWeight -= weights[i];
        currentValue -= values[i];

        // 右子树（不选择当前物品）
        backtrack(i + 1); // 递归搜索：不选择当前物品
    }

    // 从第一个物品开始搜索
    backtrack(0);

    return maxValue; // 返回最大价值
}

// 测试代码
const weights = [2, 3, 4, 5, 6, 7];  // 物品重量
const values = [3, 4, 5, 6, 7, 8];   // 物品价值
const capacity = 15;                  // 背包容量

console.log("最大背包价值为:", knapsackBacktracking(weights, values, capacity));
